#include <iostream>
#include <algorithm>

using namespace std;

// 451 根据字符出现的频率排序【中等】
// 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
//输入: s = "tree"
//输出: "eert"

class Solution {
public:
    string frequencySort(string s) {
        pair<int, char> freq[256];  // <频次，字母>
        for(int i = 0; i < 256; i++) {
            freq[i].first = 0;
            freq[i].second = i;
        }

        // 统计频次
        for (int i = 0; i < s.size(); i++)
            freq[s[i]].first++;

        sort(freq, freq+256,greater<pair<int,char> >());

        int index = 0;
        for(int i = 0; i < s.size(); i++) {
            while(freq[index].first == 0)
                index++;
            s[i] = freq[index].second;
            freq[index].first--;
        }
        return s;
//        map<char, int> records;
//        // 统计字符出现的频率
//        for(int i = 0; i < s.size(); i++)
//            records[s[i]]++;
//
//        sort(records.begin(), records.end());
//
//        for(auto iter = records.begin(); iter != records.end(); iter++)
//            cout << iter->first <<" : " << iter->second <<",";
//        cout<<endl;
//
//        return "";
    }
};

int main() {
    cout << Solution().frequencySort("tree") << endl;
    cout << Solution().frequencySort("cccaaa") << endl;
    cout << Solution().frequencySort("Aabb") << endl;

    return 0;
}
